package my.algo.data;

import java.util.Iterator;

/**
 * @author fengbo
 * @date 2018/4/16
 */
public class LinkedList<T> implements List<T> {

    private int size;

    private Node<T> first;

    private Node<T> last;

    @Override
    public boolean add(T element) {
        Node<T> itemNode = new Node<>(last, element, null);
        if (last == null) {
            first = itemNode;
        } else {
            last.next = itemNode;
        }
        last = itemNode;
        size++;
        return true;
    }

    @Override
    public boolean add(T element, int index) {
        checkIndex(index);
        if (index == size) {
            return add(element);
        }
        if (index == 0) {
            first = new Node<>(null, element, first);
        } else {
            Node<T> node = node(index - 1);
            node.next = new Node<>(node, element, node.next);
        }
        size++;
        return true;
    }

    @Override
    public T get(int i) {
        checkIndex(i);
        return node(i).item;
    }

    private Node<T> node(int index) {
        if (index < (size >> 1)) {
            Node<T> x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<T> x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public T remove(int index) {
        checkIndex(index);
        Node<T> node = node(index);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
        return node.item;
    }

    private void checkIndex(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("ArrayList index out of bounds!");
        }
    }

    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<T> {

        private int cursor = 0;
        private Node<T> next;

        Itr() {
            next = first;
        }

        @Override
        public boolean hasNext() {
            return cursor != size;
        }

        @Override
        public T next() {
            Node<T> x = next;
            next = next.next;
            cursor++;
            return x.item;
        }
    }

    private static class Node<T> {
        private T item;
        private Node<T> next;
        private Node<T> prev;

        Node(Node<T> prev, T element, Node<T> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

}
